\clearemptydoublepages
\chapter{Linux et le temps réel}
\section{Linux}
\paragraph{}
Nous allons étudier, dans cette section, pourquoi le noyau Linux n'est pas
propice à une utilisation temps réel et quelles solutions existent pour palier
ce problème.

\paragraph{}
Le premier point à aborder est pourquoi vouloir utiliser un noyau Linux plutôt
qu'un RTOS propriétaire dédié au temps réel.\\
Le noyau Linux est portable, étant utilisable sur de nombreuses plateformes.\\
Par ailleurs, les systèmes temps réel sont souvent développés par des sociétés
de tailles moyennes qui ont, de ce fait, de la peine à suivre l'évolution
technologique du matériel (pilotes) par rapport à Linux qui, par sa communauté
active, bénéficie rapidement des derniers pilotes.\\
Le code est ouvert et gratuit, ce qui permet d'y effectuer des modifications
mais aussi de faire des économies pécuniaires. De plus le noyau a fait ses
preuves en terme de fiabilité. Finalement, ce système est ouvert aux autres
systèmes. Effectivement, il permet notamment d'y exécuter des applications
Windows (Wine) et respecte la norme POSIX.

\paragraph{}
Le noyau Linux, développé par Linus Torvald en 1991, est basé sur Unix. Il a été créé à
dessein d'un usage interactif (temps d'attente minimum pour
l'utilisateur $\Rightarrow$ tranches de temps partagées).
En effet, plutôt que d'optimiser le temps de réponse d'une
application, le débit de traitement à été plébiscité. Pour ce faire, le nombre de points de
préemption a été minimisé. Les points de
préemptions ont comme désavantage d'engendrer une perte de temps en
réordonnancements et en changements de contextes.\
\paragraph{}
Ainsi, dans ses débuts, soit jusqu'à la version 2.2, le noyau Linux n'était pas
préemptif. Ceci facilitait grandement la gestion des structures puisqu'une seule
tâche noyau ne pouvait y accéder à la fois.Toutefois, ceci implique un temps de
réponse très élevé.
\paragraph{}
Depuis le noyau 2.4, la préemption noyau est devenue possible hors des
sections critiques. Cependant le problème de latence persiste,
la routine associée à une interruption matérielle, ne pouvait se déclencher
qu'après plus d'une centaine de millisecondes, devant attendre la fin de la
tâche noyau
en cours. Il était donc impossible de prédire le temps nécessaire pour qu'une
tâche noyau de plus haute priorité puisse s'exécuter.
\paragraph{}
Afin d'améliorer les performances temps réel, les développeurs ont ajouté des
points de préemptions (hook) dans la version 2.6 du noyau. Le noyau peut dès
lors s'interrompre en cours d'exécution pour passer la main à une tâche noyau plus
prioritaire.
\paragraph{}
Même si cette amélioration diminue le temps de latence à l'ordre de la
milliseconde, les sections critiques restent importantes et ne permettent donc
pas une utilisation du noyau pour du temps réel strict. 

\paragraph{}
Pour rendre le noyau Linux temps réel, plusieurs approches sont disponibles.\\ 
La première consiste à modifier le noyau en changeant l'ordonnanceur
(politique FIFO ou RR) et en y ajoutant plus de points de préemption. Cette
approche est utilisée notamment par MontaVista \cite{MontaVista:website}
(payant). Il existe aussi une version le Linux \flqq linux-rt\frqq qui améliore les performances
du noyau pour des applications temps réel. Mais qui dans ce cas reste du
temps réel tendre avec un temps de réponse de l'ordre de 200 microsecondes.\\
Le patch s'appelle PREEMPT\_RT, développé par Ingo Molnár \cite{RTPREEMPT:website}. Par ailleurs,
une image du kernel patchée est
disponible sur les distributions à base de Debian sous le nom de linux-rt.\\

Ci-dessous un schéma récapitulatif des portions non-préemptibles du noyau
Linux:

\begin{figure}[h!]
\centering
\includegraphics[scale=0.4]{../Imgs/CodeNonPremptibleLinux.png}
% CodeNonPremptibleLinux.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Code non-préemptible du noyau Linux}
\end{figure}
\FloatBarrier
\paragraph{}
Une seconde solution consiste à utiliser un noyau minimal de Linux comme
$\mu$Clinux avec un patch RT qui sans gestion de mémoire permet d'avoir des
temps de latence plus faible \cite{uClinux:website}.
\paragraph{}
La dernière solution consiste à ajouter un véritable noyau temps réel coopérant
avec le noyau Linux. Cette approche est utilisée notamment par Xenomai, RTLinux
(devenu payant) ou encore RTAI dérivé Open Source de RTLinux.\\
Par cette approche, les temps de latence sont ramenés à l'ordre de 5 à 10
microsecondes. Remarquons que par rapport au noyau Linux \flqq vanilla\frqq nous
obtenons un rapport de réduction de l'ordre de 10'000.\\
C'est donc cette solution que nous allons retenir en utilisant Xenomai.\\
Il s'agit maintenant de comprendre comment un tel noyau peut coopérer avec un
noyau Linux, ce que nous aborderons dans la section suivante.  

Les informations de cette section ont été tirées de \cite{AmeliorationLinux26}, de
\cite{SystemeTempsReel} ainsi que de \cite{CoursTempsReel},
\cite{PanoramaTempsReel}, \cite{CoursTempsReelMontreal} et enfin de
\cite{LinuxMag:website}.
	



\section{Adeos}
\paragraph{}
Dans cette section, nous allons étudier comment un noyau temps réel peut
collaborer avec un système Linux. Les diverses informations ont été tirée de la
documentation officielle d'Adeos \cite{Adeos,BuildRTOS} ainsi
que celle de Xenomai \cite{LifeAdeos} et du cours temps réel de
l'université de Marseille \cite{CoursTempsReel}.

\paragraph{}
Pour pouvoir cohabiter avec un autre noyau, comme on pouvait s'en douter, une
couche supplémentaire est nécessaire.\\
Cette couche s'appelle Adeos pour \flqq Adaptive Domain Environment for Operating
Systems\frqq et permet le partage de ressources matérielles par plusieurs systèmes
d'exploitation concurrents. Adeos ne fait pas directement partie du projet
Xenomai mais est utilisé par ce dernier. En effet, d'autres systèmes tel que RTAI
utilisent aussi cette couche.

\paragraph{}
Adeos est une couche de virtualisation des ressources, disponible sous forme
d'un patch pour le noyau Linux. Cette couche permet à plusieurs entités appelées domaines, de
s'exécuter simultanément. Les domaines ne se voient pas nécessairement entre eux. Cependant, chaque
domaine voit obligatoirement la couche Adeos.


\subsection{La communication avec le matériel}
\paragraph{}
Afin d'assurer un accès au matériel fiable et équitable entre les différents
domaines, Adeos doit prendre le contrôle de certaines commandes effectuées par
les OS mais ne doit pas non plus trop influencer le comportement standard des
OS.\\
Pour ce faire, Adeos va obliger l'OS a communiquer avec lui uniquement lorsqu'il
est nécessaire de le faire. De ce fait, Adeos fournit 4 méthodes de
communications.\\

\begin{enumerate}
\item 
La catégorie A est pour l'accès au matériel et à la mémoire sans faute de page
(aucune interruption générée). Dans cette catégorie, chaque domaine fonctionne
comme si Adeos n'existait pas.\\
\item
La catégorie B implique qu'Adeos reçoive le contrôle du matériel à cause d'une
interruption matérielle ou logicielle.\\
\item
La catégorie C représente l'invocation du gestionnaire d'interruptions de l'OS
par une exception tout en lui fournissant les informations nécessaires
quant à cette interruption. 
Si le domaine n'est pas au courant de la présence d'Adeos, il faudra alors
s'arranger pour que les interruptions ressemblent à celles attendues par l'OS en
question.\\ 
\item
Finalement, la catégorie D, implique des communications bidirectionnelles entre le
domaine et Adeos. Cependant cette catégorie n'est utilisable uniquement que si le
domaine est au courant de la présence d'Adeos. Ce type de communication permet une
utilisation optimale d'Adeos puisqu'il est alors possible à un domaine de
demander à Adeos un accès partiel ou total à des ressources occupées par un
autre domaine.\\               
\end{enumerate}

\begin{figure}[h!]
\centering
\includegraphics[scale=0.6]{../Imgs/AdeosCommunicationHardware.png}
% AdeosCommunicationHardware.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Communications entre les domaines et le matériel}
\label{fig:Adeos Communication Hardware}
\end{figure}
\FloatBarrier


\subsection{Le pipeline des événements}
\paragraph{}
Par défaut, un domaine est notifié de toutes les interruptions externes, de tous
les appels systèmes effectués par les applications Linux ou encore d'autres
événements déclenchés par le code noyau (changement de tâches, signaux, fin de
tâches, ...).
\paragraph{}
Chaque domaine possède une priorité définie statiquement. Ceci permet à Adeos de
distribuer les événements aux domaines selon l'ordre de leurs priorités en
commençant par le domaine de plus haute priorité. Pour réaliser cette
distribution, les événements sont envoyés dans un pipeline dans lequel chaque
domaine est mise en queue selon leur priorité. En mode standard, un domaine
traite l'interruption et la renvoie pour le suivant dans le pipeline.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.6]{../Imgs/AdeosPipeline.png}
% AdeosPipeline.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Pipeline des événements d'Adeos}
\label{fig:Adeos pipeline}
\end{figure}
\FloatBarrier
\paragraph{}
Remarquons que sur la figure \ref{fig:Adeos pipeline}, le noyau Linux est
considéré que le domaine racine. Ceci vient du fait que les sous-systèmes
temps réel sont intégrés sous la forme de modules noyau, du noyau Linux.
\paragraph{}
Afin que chaque domaine puisse utiliser des sections critiques, Adeos utilise
\flqq la protection d'interruptions optimiste\frqq
\cite{OptimisticInterrput:website}.
\paragraph{}
Pour ce faire, l'étape où le pipeline est occupé par un domaine donné peut être
gelée. Ce qui signifie que l'arrivée de la prochaine interruption ne sera pas
livrée au domaine et ne descendra pas non plus, plus bas, dans le pipeline. En
effet, les événements sont mis en suspend dans le journal des interruptions du
domaine. Ces interruptions peuvent être ensuite jouées lorsque le domaine n'est
plus bloqué (synchronisation). Il est aussi possible de simplement rejeter
l'interruption qui continuera alors sa descente dans le pipeline ou encore de la
terminer ce qui stoppera sa propagation.
\paragraph{}
Les domaines peuvent utiliser cette technique afin de protéger leurs sections
critiques d'une éventuelle préemption par leur propre gestionnaire
d'interruption. Cependant, puisque les domaines sont mis en queue selon leurs
priorités, un domaine de plus haute priorité tel qu'un noyau temps réel,
continue de recevoir les interruptions, sans délai supplémentaire.
\paragraph{}
Notons que les événements générés par le système telles que les fautes de pages
peuvent aussi se propager par le pipeline mais ne peuvent être suspendus de par
leur caractère synchrone.

\begin{figure}[h!]
\centering
\includegraphics[scale=0.6]{../Imgs/InterruptionAdeos.png}
% InterruptionAdeos.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Système de propagation des interruptions avec Adeos}
\label{fig:InterruptionAdeos}
\end{figure}
\FloatBarrier
\paragraph{}
Une fois que tous les domaines ont été traités, Adeos vérifie si tous ces
domaines sont dans l'état \textit{dormant}. Si tel est le cas, Adeos invoque sa tâche
nulle qui reste active jusqu'à la prochaine interruption. Dans le cas contraire,
il reprend l'exécution du processus qui était en cours avant l'interruption.

\paragraph{}
En résumé, le système temps réel sera donc capable de recevoir tous les
événements en premier et de les trier. De plus ce dernier ne pourra être
interrompu par une tâche Linux, ni par le noyau lui même.\\



\section{Xenomai}
Nous verrons, dans cette section, l'architecture de Xenomai ainsi que ses
différents modes.
\paragraph{}
\textit{Xenomai est un framework de développement temps réel strict intégré dans
l'environnement Linux et coopérant avec ce dernier. Il permet l'utilisation
d'applications dans l'espace utilisateur qui n'ont pas besoin d'être dépendante
d'une interface particulière} \cite{SiteXenomai:website}.

\subsection{Les skins}
\paragraph{}
Comme cité dans le précédent paragraphe, les applications n'ont pas besoin
d'être dépendantes d'une interface particulière, car Xenomai utilise un système
de \textit{skins}. Un skin est une interface de programmation, permettant d'émuler un
système temps réel. Ceci a été créé dans le but de faciliter l'interopérabilité
et la migration entre les applications codées sur d'autre RTOS que Xenomai.\\
Tous ces skins utilisent évidemment le même noyau, \textit{nucleus}, de Xenomai.\\

Voici la liste des systèmes pour lesquels Xenomai ont prévu un skin :

\begin{itemize}
\item POSIX (Portable Operating System Interface)
\item PSOS+ (WindRiver pSOS+)
\item RTAI (RealTime Application Interface for Linux)
\item µITRON (Spécifications µITRON)
\item VRTX (Versatile Real-Time Executive)
\item vxWorks
\end{itemize}

\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{../Imgs/SkinsXenomai.png}
% SkinsXenomai.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Skins de Xenomai }
\end{figure}
\FloatBarrier
De plus, Xenomai possède aussi une interface native.
\paragraph{}
Comme nous avons pu l'apercevoir dans la section précédente, Xenomai va
s'appuyer sur Adeos pour lui fournir les événements en premier (avant le noyau
Linux) et ceci immédiatement quoi que le noyau Linux soit en train d'effectuer.\\
\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{../Imgs/XenomaiAdeos.png}
% XenomaiAdeos.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Couches Xenomai et Adeos}
\end{figure}
\FloatBarrier
Le noyau Linux est en fait la tâche nulle du noyau temps-réel. 

\subsection{Espaces d'exécution}
\paragraph{}
Xenomai, possède quelques bibliothèques de base proposant notamment la création
de tâches temps réel et de sémaphores temps réel.\\
Toutefois, le but de Xenomai est bien de coopérer avec le noyau Linux et donc
de pouvoir utiliser les bibliothèques de Linux sans devoir les
réimplémenter.\\
Mais il serait aussi insensé d'utiliser ces bibliothèques en perdant la
priorité temps réel de la tâche.
\paragraph{}
Pour résoudre ce problème, les concepteurs de Xenomai ont eu l'idée géniale de
pouvoir faire migrer une tâche s'exécutant dans l'espace utilisateur de Xenomai
à l'espace utilisateur Linux. En effet, lors d'un appel à une
bibliothèque Linux (effectuant un appel système) depuis une tâche s'exécutant
dans l'espace Xenomai, la tâche
est automatiquement migrée dans l'espace utilisateur Linux, tout en gardant sa
priorité, en faisant hériter au noyau Linux sa priorité temps réel.\\
Une fois que la tâche refait appel à une bibliothèque de Xenomai, la tâche
remigre alors dans son espace originel.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.5]{../Imgs/MigrationTask.png}
% MigrationTask.png: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb=
\caption{Migration de l'espace Xenomai à l'espace Linux}
\end{figure}
\FloatBarrier
\paragraph{}
De ce fait, une tâche peut être exécutée dans 3 espaces différents. L'espace
utilisateur Xenomai et Linux, discuté ci-avant mais aussi l'espace noyau
Xenomai, utile pour la création de pilotes par exemple.
\paragraph{}
En plus de la migration automatique de l'espace utilisateur de Xenomai vers
l'espace utilisateur Linux, l'API de Xenomai offre une fonction permettant de
faire migrer manuellement une tâche définie dans l'espace utilisateur Linux à
l'espace utilisateur de Xenomai.

\paragraph{}
Le choix s'est porté sur Xenomai notamment, grâce à cette possibilité de
migration mais aussi pour ses temps de réponse très performants, sa facilité
d'installation, ses multiples interfaces de programmations (skins), mais aussi
car le projet est soutenu activement (mises à jour,...).

\paragraph{}
La problématique du choix d'un système temps réel résolue, nous pouvons maintenant passer
à la problématique même du projet, l'économie d'énergie, thème du prochain
chapitre.



































